package com.isaiah.graph.adjacencylist;


import com.isaiah.queue.Queue;

import java.util.LinkedList;

/**
 * @Title: 加权无向图
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/6/611:35
 */
public class EdgeWeightedGraph {
    /** 顶点总数 */
    private final int V;
    /** 边的总数 */
    private int E;
    /** 邻接表 */
    private LinkedList<Edge>[] adj;

    public EdgeWeightedGraph(int v) {
        /** 顶点的总数 */
        this.V = v;
        /** 边的总数 */
        this.E = 0;
        // 初始化邻接表
        adj = new LinkedList[v];
        for (int i = 0; i < adj.length; i++){
            adj[i] = new LinkedList<>();
        }
    }

    /**
     * 获取图中的顶点数
     * @return
     */
    public int v(){
        return V;
    }

    /**
     * 获取图中边的数量
     * @return
     */
    public int E(){
        return E;
    }

    public void addEdge(Edge e){
        // 需要让边e同时出现在e这个边的两个顶点的邻接表中
        int v = e.either();
        int w = e.other(v);
        adj[v].addFirst(e);
        adj[w].addFirst(e);
        // 维护边数量
        E++;
    }

    /**
     * 获取和顶点v关联的所有边
     * @param v
     * @return
     */
    public LinkedList<Edge> adj(int v){
        return adj[v];
    }

    public LinkedList edges(){
        LinkedList<Edge> allEdges = new LinkedList<>();
        // 遍历国的每个一顶点，找到顶点的邻接表，邻接表中存储了该顶点的关联的每一条边
        for (int v = 0; v < V; v++){
            LinkedList<Edge> adj = adj(v);
            for (Edge e : adj(v)){
                // 因为这是无向图，所以一条边同时出现在了它关联两个顶点的邻接表中，需要让一条边只记录一次
               if (e.other(v) < v){
                   allEdges.addFirst(e);
               }
            }
        }
        return allEdges;
    }
}

class Edge implements Comparable<Edge>{
    /** 顶点一 */
    private final int v;
    /** 顶点二 */
    private final int w;
    /** 当前边的权重 */
    private final double weight;

    /**
     * 通过顶点v和w，以及权重weight值构造一个边
     * @param v
     * @param w
     * @param weight
     */
    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public double getWeight() {
        return weight;
    }

    /**
     * 获取边的一个顶点
     * @return
     */
    public int either(){
        return v;
    }

    /**
     * 获取边上除了顶点vertex外的另外一个顶点
     * @param vertex
     * @return
     */
    public int other(int vertex){
        if (vertex == v){
            return w;
        }else{
            return v;
        }
    }

    @Override
    public int compareTo(Edge other) {
        // 如果当前边的权重值大，则返回1
        if (this.getWeight() > other.getWeight()){
            return 1;
        }
        // 如果当前边的权重值小，则返回-1
        else if (this.getWeight() < other.getWeight()){
            return -1;
        }
        // 如果当前边的权重值和other边的权重值一样大，则返回0
        else{
            return 0;
        }
    }
}
